package leetcode.L500;

public class EX92 {
      public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

//    public static ListNode reverseBetween(ListNode head, int left, int right) {
//        if(left==right){
//            return head;
//        }
//        ListNode prv = new ListNode(-1);
//        prv.next = head;
//
//        ListNode star = prv;
//        ListNode end = prv;
//        for(int i = 1;i<left;i++){
//            star = star.next;
//        }
//        ListNode beforeStar = star;
//        star = star.next;
//
//        for(int i = 0;i<right;i++){
//            end = end.next;
//        }
//        ListNode afterEnd = end.next;
//
//        ListNode first = star;
//        ListNode second = star.next;
//        ListNode th = second.next;
//
//        while(second!=end){
//            second.next = first;
//            first = second;
//            second = th;
//            th = th.next;
//        }
//
//        second.next = first;
//        beforeStar.next = second;
//        star.next = afterEnd;
//        return prv.next;
//    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right){
            return head;
        }
        ListNode dumy = new ListNode(-1);
        dumy.next = head;
        ListNode rightNode = dumy;
        ListNode leftNodePre = dumy;
        for(int i = 0;i<right;i++){
            rightNode = rightNode.next;
        }
        for(int i = 0;i<left-1;i++){
            leftNodePre = leftNodePre.next;
        }
        ListNode pre = leftNodePre.next;
        ListNode cur = pre.next;
        while(cur!=rightNode.next){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        leftNodePre.next = rightNode;
        rightNode.next = leftNodePre;
        return dumy.next;

    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode now = head;

        for (int i = 2; i <= 5 ; i++) {
            now.next = new ListNode(i);
            now = now.next;
        }


        reverseBetween(head,2,4);
        while(head!=null){
            System.out.println(head.val);
            head = head.next;
        }

    }

}
